﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace MoPhongThuatToan
{
    class Dijkstra
    {
        private int VOCUC = 1000000000;
        private int n;
	    private int[,] L=new int [100,100];//ma tran
	    private int[] T=new int[10000];
	    private int nT;
	    private int[] D=new int[10000];//
	    private int[] Label=new int[10000];//mang luu dinh truoc dinh t
	    private int s;//bat dau
	    private int t;//ket thuc
        public void NhapFile(String FilePath)
        {
            FileStream fs = new FileStream(FilePath, FileMode.Open);
            StreamReader sr = new StreamReader(fs);
            n = Convert.ToInt32(sr.ReadLine());
            s = Convert.ToInt32(sr.ReadLine());
            t = Convert.ToInt32(sr.ReadLine());
            for (int i = 0; i < n; i++)
            {
                string Line = sr.ReadLine();
                string[] G = Line.Split(new char[] { ' ' });
                for (int j = 0; j < n; j++)
                {
                    L[i, j] = int.Parse(G[j]);
                }
            }
            sr.Close();
            fs.Close();
        }
        public void XuatFile(string FilePath)
        {
            FileStream fs = new FileStream(FilePath, FileMode.Create);
            StreamWriter sw = new StreamWriter(fs);
            //sw.WriteLine(n);
            //for (int i = 0; i < n; i++)
            //{
            //    for (int j = 0; j < n; j++)
            //    {
            //        sw.Write(a[i, j]);
            //        sw.Write("\t");
            //    }
            //    sw.Write("\n");
            //    sw.Write(sw.NewLine);
            //}            
            //int dem = D[t];
            //sw.Write(dem);
            //sw.Write("\n");
            int k = t;
            while (k != s)
            {
                sw.Write(k);
                sw.Write("\t");
                k = Label[k];
            }
            sw.Write(s);
            sw.Close();
            fs.Close();
        }
        public void KhoiTao()
        {
            nT=n;//V=X
            for(int i=0;i<n;i++)//voi moi k thuoc X bo di s
            {
	            T[i]=1;//tat cac cac dinh deu nam trong T
	            D[i]=VOCUC;//D[k]
	            Label[i]=-1;
            }
            D[s]=0;
        }
        public void DijkstraAlg(int j)
        {
	        KhoiTao();
	        int v=s;
	        int min;
	        while(T[t]==1)
	        {
		        min=VOCUC;
		        v=-1;
		        for(int i=0;i<nT;i++)
		        {
			        if(T[i]!=0 && min>D[i])
			        {
				        min=D[i];
				        v=i;
			        }
		        }
		        if(v == -1)
			        return;
		        T[v]=0;
		        for(int k=0;k<nT;k++)
		        {
			        if(L[v,k]!=0 && D[k]>D[v]+L[v,k])
			        {
				        D[k]=D[v]+L[v,k];
				        Label[k]=v;
			        }
		        }
	        }
        }
    }
}
